package lib

import (
	"math"
)

func init() {
	Probs = append(Probs, Problem{
		Num:         1262,
		Discription: "数组中元素之和能被3整除的最大和",
		Level:       2,
		Labels: map[string]int{
			"动态规划":  1,
			"有限状态机": 1,
		},
	})
}

func MaxSumDivThree(nums []int) int {
	n := len(nums)
	//dp[i][j]表示nums[:i]中除3余j的最大和
	dp := make([][3]int, n+1)
	//如果什么元素都不选的话，是没法求余得到1或者2的，所以需要把这两个位置的值置为int32的最小，保证后面的状态不会由这个状态转化而来
	dp[0] = [3]int{0, math.MinInt32, math.MinInt32}
	for i := 1; i <= n; i++ {
		val := nums[i-1]
		var sums [3]int
		for j := 0; j < 3; j++ {
			//dp[i-1][(val+j)%3]表示不用nums[i]得到这个余数
			//dp[i-1][j]+val表示用了nums[i]得到这个余数
			sums[(val+j)%3] = max(dp[i-1][(val+j)%3], dp[i-1][j]+val)
		}
		dp[i] = sums
	}

	return dp[n][0]
}
